【题解】 货车运输 最大生成树+倍增Lca luoguP1967 | Qiuly's blog!

【题解】 货车运输 最大生成树+倍增Lca luoguP1967

Posted on | Edited on | In | Comments:

题目大意就是，有多组询问，每组询问包含两个整数 $x,y​$ ，求出 $x​$ 到 $y​$ 的一条路径，满足这条路径在所有的 $x​$ 到 $y​$ 的路径中，边权最小的边权值最大。

这个很显然我们可以先求出图的最大生成树，那么 $x$ 到 $y$ 的目标路径肯定在最大生成树上，也只能在最大生成树上。

那么我们需要在最大生成树上找到这条路径，最大生成树是一棵树，很显然的我们可以想到在这棵树上做 $Lca$ ，那么这样就超级简单了。

我们在求 $lca$ 的时候顺带维护一下 $sum$ 数组，$sum[x][i]$ 表示在最大生成树 $x$ 到 $fa[x][i]$ 这条路径上的所有边的边权最小值。转移的方法也很简单：$sum[x][i]=min(sum[x][i-1],sum[fa[x][i-1]][i-1])$ 。

对于不能到达的情况特判一下就好了。

于是这题就做完了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<queue>
#include<string>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
    
#define ll long long
#define A printf("A")
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define swap(x,y) ((x)^=(y)^=(x)^=(y))

const int N=1e5+2;
const int log=30;
const int inf=1e9+9;

int n,m,q,cnt,f[N];
int dep[N],fa[N][log+2],sum[N][log+2];
struct Edge{int from,to,val;}G[N<<1];
std::vector<int> E[N],V[N];

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

bool cmp(Edge a,Edge b){return a.val>b.val;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

void dfs(int u,int f,int dis){
    dep[u]=dep[f]+1,
    fa[u][0]=f,sum[u][0]=dis;
    for(int i=1;i<log;++i)
        fa[u][i]=fa[fa[u][i-1]][i-1],
        sum[u][i]=min(sum[u][i-1],sum[fa[u][i-1]][i-1]);
    int size=E[u].size();
    for(int i=0;i<size;++i){
        int v=E[u][i];
        if(v!=f)dfs(v,u,V[u][i]);
    }return;
}

inline int solve(int x,int y){
    int ans=inf;
    if(dep[x]<dep[y])swap(x,y);
    for(int i=log-1;i>=0;--i)
        if(dep[fa[x][i]]>=dep[y])
            ans=min(ans,sum[x][i]),x=fa[x][i];
    if(x==y)return ans;
    for(int i=log-1;i>=0;--i)
        if(fa[x][i]!=fa[y][i]){
            ans=min(ans,min(sum[x][i],sum[y][i]));
            x=fa[x][i],y=fa[y][i];
        }
    ans=min(ans,min(sum[x][0],sum[y][0]));
    if(fa[x][0]==0)return -1;
    else return ans;
}

int main(){
    IN(n),IN(m);
    for(int i=1;i<=n;++i)f[i]=i;
    for(int i=1;i<=m;++i)
        IN(G[i].from),IN(G[i].to),IN(G[i].val);
    std::sort(G+1,G+1+m,cmp);
    for(int i=1;i<=m;++i){
        int fx=find(G[i].from),fy=find(G[i].to);
        if(fx!=fy){
            f[fy]=fx;++cnt;
            E[G[i].from].push_back(G[i].to),V[G[i].from].push_back(G[i].val);
            E[G[i].to].push_back(G[i].from),V[G[i].to].push_back(G[i].val);
            if(cnt==n-1)break;
        }
    }
    for(int i=1;i<=n;++i)
        if(!dep[i])dfs(i,0,0);
    IN(q);
    for(int i=1;i<=q;++i){
        int x,y;IN(x),IN(y);
        printf("%d\n",solve(x,y));
    }
    return 0;
}

本文标题:【题解】 货车运输 最大生成树+倍增Lca luoguP1967

文章作者:Qiuly

发布时间:2019年03月13日 - 00:00

最后更新:2019年03月29日 - 13:53

原始链接:http://qiulyblog.github.io/2019/03/13/[题解]luoguP1967/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。